package com.c2b.algorithm.leetcode.lcr;

/**
 * <a href="https://leetcode.cn/problems/reorder-list/">重排链表</a>
 * <p>给定一个单链表 L 的头节点 head ，单链表 L 表示为：</p>
 * <pre>L0 → L1 → … → Ln - 1 → Ln</pre>
 * <p>请将其重新排列后变为：</p>
 * <pre>L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …</pre>
 * <br><b>不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4]
 *      输出：[1,4,2,3]
 *
 * 示例 2：
 *      输入：head = [1,2,3,4,5]
 *      输出：[1,5,2,4,3]
 * </pre>
 * <b>提示：</b>
 * <li>链表的长度范围为 [1, 5 * 10^4]</li>
 * <li>1 <= node.val <= 1000</li>
 *
 * @author c2b
 * @since 2024/3/19 17:45
 */
public class LCR026 {
    static class Solution {
        public void reorderList(ListNode head) {
            // 找到中间节点
            ListNode fast = head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode list1 = head;
            ListNode list2 = slow.next;
            slow.next = null;
            // 反转链表
            list2 = reserve(list2);
            // 合并链表
            while (list1 != null && list2 != null) {
                ListNode tempNode1 = list1.next;
                ListNode tempNode2 = list2.next;
                list1.next = list2;
                list1 = tempNode1;
                list2.next = list1;
                list2 = tempNode2;
            }
        }

        private ListNode reserve(ListNode head) {
            ListNode prevNode = null;
            ListNode currNode = head;
            ListNode nextNode;
            while (currNode != null) {
                nextNode = currNode.next;
                currNode.next = prevNode;
                prevNode = currNode;
                currNode = nextNode;
            }
            return prevNode;
        }
    }
}
